package com.linxcool.util;

import java.util.LinkedHashMap;
import java.util.Locale;
import java.util.Map;

/**
 * 支持LRU缓存的哈希表
 * <p><b>Time:</b> 2013-12-2
 * @author 胡昌海(linxcool.hu)
 * @param <K>
 * @param <V>
 */
public class LruCacheMap<K, V> extends LinkedHashMap<K, V>{

	private static final long serialVersionUID = 1L;

	private int size;
	private int maxSize;

	private int putCount;
	private int createCount;
	private int evictionCount;
	private int hitCount;
	private int missCount;
	
	Entry<K, V> eldest;

	public LruCacheMap(int maxSize) {
		super(0, 0.75f, true);
		if (maxSize <= 0)
			throw new IllegalArgumentException("maxSize <= 0");
		this.maxSize = maxSize;
	}

	public final V get(Object k) {
		if (k == null)
			throw new NullPointerException("key == null");

		@SuppressWarnings("unchecked")
		K key = (K) k;
		V mapValue;
		synchronized (this) {
			mapValue = super.get(key);
			if (mapValue != null) {
				hitCount++;
				return mapValue;
			}
			missCount++;
		}

		V createdValue = create(key);
		if (createdValue == null)
			return null;

		synchronized (this) {
			createCount++;
			mapValue = super.put(key, createdValue);
			if (mapValue != null) super.put(key, mapValue);
			else size += safeSizeOf(key, createdValue);
		}

		if (mapValue != null) {
			entryRemoved(false, key, createdValue, mapValue);
			return mapValue;
		}
		else {
			trimToSize(maxSize);
			return createdValue;
		}
	}

	public final V put(K key, V value) {
		if (key == null || value == null)
			throw new NullPointerException("key == null || value == null");

		V previous;
		synchronized (this) {
			putCount++;
			size += safeSizeOf(key, value);
			previous = super.put(key, value);
			if (previous != null) {
				size -= safeSizeOf(key, previous);
			}
		}

		if (previous != null)
			entryRemoved(false, key, previous, value);

		trimToSize(maxSize);
		return previous;
	}

	private void trimToSize(int maxSize) {
		while (true) {
			K key;
			V value;
			synchronized (this) {
				if (size < 0 || (super.isEmpty() && size != 0)) 
					throw new IllegalStateException("sizeOf() is reporting inconsistent results!");
				if (size <= maxSize)
					break;

				Map.Entry<K, V> toEvict = eldest();
				if (toEvict == null) 
					break;

				key = toEvict.getKey();
				value = toEvict.getValue();
				super.remove(key);
				size -= safeSizeOf(key, value);
				evictionCount++;
				
				eldest = null;
				if(size <= maxSize || isEmpty())
					break;
				key = keySet().iterator().next();
				value = super.get(key);
				super.put(key, value);
			}
			entryRemoved(true, key, value, null);
		}
	}

	public Entry<K, V> eldest() {
		return eldest;
	}

	@Override
	protected boolean removeEldestEntry(Entry<K, V> eldest) {
		this.eldest = eldest;
		return super.removeEldestEntry(eldest);
	}

	public final V remove(Object k) {
		if (k == null) {
			throw new NullPointerException("key == null");
		}

		@SuppressWarnings("unchecked")
		K key = (K) k;
		V previous;
		synchronized (this) {
			previous = super.remove(key);
			if (previous != null) {
				size -= safeSizeOf(key, previous);
			}
		}

		if (previous != null) 
			entryRemoved(false, key, previous, null);

		return previous;
	}

	/**
	 * Called for entries that have been evicted or removed. This method is
	 * invoked when a value is evicted to make space, removed by a call to
	 * {@link #remove}, or replaced by a call to {@link #put}. The default
	 * implementation does nothing.
	 *
	 * <p>The method is called without synchronization: other threads may
	 * access the cache while this method is executing.
	 *
	 * @param evicted true if the entry is being removed to make space, false
	 *     if the removal was caused by a {@link #put} or {@link #remove}.
	 * @param newValue the new value for {@code key}, if it exists. If non-null,
	 *     this removal was caused by a {@link #put}. Otherwise it was caused by
	 *     an eviction or a {@link #remove}.
	 */
	protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

	/**
	 * Called after a cache miss to compute a value for the corresponding key.
	 * Returns the computed value or null if no value can be computed. The
	 * default implementation returns null.
	 *
	 * <p>The method is called without synchronization: other threads may
	 * access the cache while this method is executing.
	 *
	 * <p>If a value for {@code key} exists in the cache when this method
	 * returns, the created value will be released with {@link #entryRemoved}
	 * and discarded. This can occur when multiple threads request the same key
	 * at the same time (causing multiple values to be created), or when one
	 * thread calls {@link #put} while another is creating a value for the same
	 * key.
	 */
	protected V create(K key) {
		return null;
	}

	private int safeSizeOf(K key, V value) {
		int result = sizeOf(key, value);
		if (result < 0) {
			throw new IllegalStateException("Negative size: " + key + "=" + value);
		}
		return result;
	}

	/**
	 * Returns the size of the entry for {@code key} and {@code value} in
	 * user-defined units.  The default implementation returns 1 so that size
	 * is the number of entries and max size is the maximum number of entries.
	 *
	 * <p>An entry's size must not change while it is in the cache.
	 */
	protected int sizeOf(K key, V value) {
		return 1;
	}

	/**
	 * Clear the cache, calling {@link #entryRemoved} on each removed entry.
	 */
	public final void evictAll() {
		trimToSize(-1); // -1 will evict 0-sized elements
	}

	/**
	 * For caches that do not override {@link #sizeOf}, this returns the number
	 * of entries in the cache. For all other caches, this returns the sum of
	 * the sizes of the entries in this cache.
	 */
	public synchronized final int currentSize() {
		return size;
	}

	/**
	 * For caches that do not override {@link #sizeOf}, this returns the maximum
	 * number of entries in the cache. For all other caches, this returns the
	 * maximum sum of the sizes of the entries in this cache.
	 */
	public synchronized final int maxSize() {
		return maxSize;
	}

	/**
	 * Returns the number of times {@link #get} returned a value that was
	 * already present in the cache.
	 */
	public synchronized final int hitCount() {
		return hitCount;
	}

	/**
	 * Returns the number of times {@link #get} returned null or required a new
	 * value to be created.
	 */
	public synchronized final int missCount() {
		return missCount;
	}

	/**
	 * Returns the number of times {@link #create(Object)} returned a value.
	 */
	public synchronized final int createCount() {
		return createCount;
	}

	/**
	 * Returns the number of times {@link #put} was called.
	 */
	public synchronized final int putCount() {
		return putCount;
	}

	/**
	 * Returns the number of values that have been evicted.
	 */
	public synchronized final int evictionCount() {
		return evictionCount;
	}

	/**
	 * Returns a copy of the current contents of the cache, ordered from least
	 * recently accessed to most recently accessed.
	 */
	public synchronized final Map<K, V> snapshot() {
		return new LinkedHashMap<K, V>(this);
	}

	@Override
	public synchronized final String toString() {
		int accesses = hitCount + missCount;
		int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
		return String.format(
				Locale.getDefault(),
				"LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
				maxSize, 
				hitCount, 
				missCount, 
				hitPercent);
	}
}

